Unusual number bases, including Fibonacci and the irrational Phi bases, factorials and binomial coefficients bases,
rational number bases, negative bases, negative "digits", with interactive Calculators for all of these.
The calculators on this page require JavaScript but you appear to have switched JavaScript off
(it is disabled). Please go to the Preferences for this browser and enable it if you want to use the
calculators, section links and other interactive features, then Reload this page.
Contents of this page
The icon means there is a
You Do the Maths... section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that section.
With thanks to MikeMcl and his BigNumbers JS library
(readMe hosted on github).
It is used here in the JavaScript Calculators
for arbitrary precision number calculations.
Representing whole numbers in different bases
If you are familiar with bases 2,3,... then skip to the next section.
Otherwise begin here for basic information on bases.
We normally write numbers in base 10 so that each digit counts a power of 10 in the value:
2017 = 2×103 + 0×102 +1×101 + 7×100
The word digit means "finger".
In the American and UK systems of measuring liquids in pints and gallons,
there are 8 pints to 1 gallon, so 20 pints represents 2 gallons and 4 pints.
It used to be the case that 8 gallons make 1 bushel in the UK but
the American and British systems
are now different.
This is a base 8 system where we counts in 8s:
90 pints is 1×82 + 3×8 + 2: 90 in base 10 is 132 in base 8
Digits
We see that in base 10 (the decimal system), we need only 10 symbols, the digits0, 1, 2, 3, 4, 5, 6, 7, 8 and 9.
In Base 8 (octal) we need only the 8 symbols 0, 1, 2, 3, 4, 5, 6, 7
because 8 in one column will convert into 1 in the next higher column.
Similarly in base β we need only β symbols for the digits, one digit per column.
So what if the base is bigger than 10?
Computer engineers often use this since computers work in Base 2 (Binary) using binary-digits0, 1
and it was often more convenient to use base 16 (hexadecimal) using the "digits"
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
In base β we need only β 'digit' symbols
To show what base a number is in, we write its base as a suffix after the number representation, e.g.:
90 = 1328 10 = 128 7 = 125
If we omit the base then the base used is 10.
Names of Bases
base 2binary
base 3 ternary, trinary
base 4 quaternary
base 5 quintal, quinary
base 6 sextal, senary
base 7 septal, septenary
base 8 octal
base 9 nonary
base 10 decimal, denary
base 11 undecimal
base 12 duodecimal
base 16 hexadecimal
base 20 vigesimal
base 30 trigesimal
base 40 quadragesimal
base 50 quinquagesimal
base 60 sexagesimal
base 70 septuagesimal, septagesimal
base 80 octagesimal
base 90 nonagesimal, nonogesimal
base 100 centesimal
The vigesimal system was used by the Mayan civilisation in central America and also in Britain where 20 is called a "score".
Other cultures used a base 5 system (New Hebrides) or a binary system. 12 (duodecimal) was also popular because it is easy to divide by 2, 3 and
4 and the ancient Babylonians used base 60 (sexagesimal) because it was also easy to divide by 2, 3, 4 and 5.
The system of money used in Britain from the 8th century until 1971 was a mixed-base system with
12 pence in a shilling and 20 shillings in a pound (£).
The names of the number bases are not used much on these pages, just base 12 or base 20 for example instead.
An easy method to convert a number to and from base β
Let's look at an example.
To convert a (decimal) number to base 6, say, keep dividing the number by 6 recording any remainders. The remainders become the base 6
representation of the number.
We start with 6 dividing 5755 and work upwards , repeatedly dividing the quotients until we reach 0
0
rem = 4
6
4
rem = 2
4 = 6×0 + 4
6
26
rem = 3
26 = 6×4 + 2
6
159
rem = 5
159 = 6×26 + 3
6
959
rem = 1
959 = 6×159 + 5
6
5755
5755 = 6×959 + 1
To see the base 6 representation, write down the remainders from the top to the bottom: 5755 = 423516
This works for any numeric base and shows that the 'digits' of base β must be 0,1,2,...,β-1 because they are the remainders on
dividing by β.
Because we repeat the process on the quotients until we reach 0, we can see the 'digits' of the quotients too:
To convert a number from base β to decimal we reverse the process,
starting with the leftmost digit and continually multiplying it by the base β and adding in the next digit:
Here we convert 42356 to base 10, accumulating a final sum as we go from left to right across the 'digits':
by multiplying each power of x individually by its coefficient, it is much easier and more efficient if we accumulate the sum by using Horner's rule:
P(x) = ((..( ( an) x + an−1 ) x + ... + a1) x + a0
So to evaluate 42356 = 4×63
+ 2×62
+ 3×6 + 5, we calculate instead:
((4×6 + 2)×6
+ 3)×6 + 5
which is what we are doing in the table method of the previous subsection.
The Art of Computer Programming, Vol 2:Seminumerical Algorithms D E Knuth
(first edition 1981, third edition 1998) section 4.6.4 Evaluation of Polynomials
Factorial base
Permutations
Instead of using powers of a number as the column headings, we can use other series of numbers too, for instance the factorials.
The factorial numbers count the number of permutations of n objects.
In general, whatever the objects, they will be in first place, second place and so on in the permutation list.
So we can just use their positions 1,2, ... ,n as the objects and name the objects 1,2,...,n.
So the ways to permute 3 objects (to arrange them all in some order)
are: 123, 132, 213, 231, 312, 321.
If we were permuting the letters of CAT we use 1 for C, 2 for A and 3 for T. Ther 6 permutations are therefore:
123=CAT, 132=CTA, 213=ACT, 231=ATC, 312=TAC, 321=TAC
Why are there exactly 6 permutations?
Because there are 3 ways to choose the position in which to put it including where it is now.
There are 2 position for the second object and then the third object goes in the remaining empty place: 3x2x1=6.
Similar reasoning shows there are 4×3×2×1 permutations
of 4 objects.
For n objects there are n! = n×(n−1)×...×3×2×1 permutations, called
factorial n, also written as n!.
n
1
2
3
4
5
6
7
8
9
10
n!
1
2
6
24
120
720
5040
40320
362880
3628800
A Factorial-base system
The factorial numbers can be used as the columns of a mixed base system,
arranging them in reverse order: ..., 5!, 4!, 3!, 2!, 1!. The digits allowed in each column depend on the column number:
the first column (1!) can have 0 or 1;
the second column (2!) can have digits 0, 1 or 2;
and in general the n-th factorial column can have 0,1, up to the column number n.
This is because n in column n means n×n! but (n+1)×n! is (n+1)!,
which "carries" to the next larger column heading (on the left).
To indicate numbers in this base, we list the "digits" and use the exclamation mark "!" as the base. For larger number using ten or more columns, the value in a column may be 10 or more.
Here we will write the values (numbers) in each factorial column as a list of numbers enclosed in { } brackets.
Easy methods of converting to and from the Factorial Base
To convert a number to base !:
We can adapt the easy method to convert a number to base β above for converting
a (decimal) number to base !. This time we start by dividing by 2 and the divisor increases each time.
Here is an example to convert 69 to base !:
2
69
3
34
rem=1
69 = 2×34 + 1
4
11
rem=1
34 = 3×11 + 1
5
2
rem=3
11 = 4×2 + 3
0
rem=2
2 = 5×0 + 2
To see the base ! representation, write down the reminders from the bottom to the top: 69 = 2311!
To convert a base ! representation to decimal:
First write the multipliers above each digit by starting from the right with 2
and proceed leftwards with multipler 3 then 4 and so on.
We will not use the leftmost 'multiplier' above the leftmost digit.
Start with the most significant digit (the leftmost digit) which is the initial 'sum'
Multiply the sum by the next column multiplier on its right ...
... and then add on the 'digit' under that multiplier to make the new 'sum'
Repeat the previous two steps of multiplying and adding
until you have a 'sum' under the final (rightmost) digit which is the decimal value
For example, using the same numbers as the example above, we have:
To convert 2311! to decimal:
Every factorial from n! onwards is a multiple of n.
So to test if any given factorial base representation is divisible by n, we only need to test the number represented by the
last n−1 'digits'.
For instance, to test if n! is divisible by 2=2!,
look only at the last 'digit'. If it is 0, n is even, divisible by 2; if it is 1, the number is odd.
For divisibility by 3, test only the last 2 'digit's. if they are {1,1}! or
{0,0}! then n is a multiple of 3; otherwise it is not.
There are 6 possibilities for the final 3 'digits' to test if a value is a multiple of 4.
Show them
For larger divisors d, convert only the final d digits to base 10 and then test.
These divisibility tests are an advantage only if we are dealing with very large numbers and testing for small divisors.
An Application of Base Factorial
The 24 permutations of 4 objects can be listed in lexicographic order which means that the permutations,
as numbers, are in numerical order or dictionary or alphabetic order. For instance here is the order of all the permutations of
1,2,3 and 4 sorted into lexicographic (dictionary) order - think of 1 as "a", 2 as "b", 3 as "c" and 4 as "d":
0:
1,2,3,4
1:
1,2,4,3
2:
1,3,2,4
3:
1,3,4,2
4:
1,4,2,3
5:
1,4,3,2
6:
2,1,3,4
7:
2,1,4,3
8:
2,3,1,4
9:
2,3,4,1
10:
2,4,1,3
11:
2,4,3,1
12:
3,1,2,4
13:
3,1,4,2
14:
3,2,1,4
15:
3,2,4,1
16:
3,4,1,2
17:
3,4,2,1
18:
4,1,2,3
19:
4,1,3,2
20:
4,2,1,3
21:
4,2,3,1
22:
4,3,1,2
23:
4,3,2,1
If we want to choose a random permutation or if we want to make sure we go through all permutations, we need a way of changing the number
of the permutation in the lexicographic order to the permutation itself - and this is where base Factorial comes in.
The base factorial
representation of an index number n in the lexicographic order is easily changed into the permutation itself.
Calculator for Factorial Base and Permutations
Show the factorial of
find the exact complete factorial.
As a guide to timings, it may take about 1 second to compute 9000!
and about 30 seconds to compute 40000! Beware of putting in a large number n to find n! exactly (top button)!.
Show the end sig. figs of factorial of
The final 10 significant figures are shown with a count of the number of zeroes that end
all factorials beyond 5.
These can be computed quickly even for extremely large values of n;
the final digits of 1000000! take about 10 second to find.
Show # digits in the factorial of
This is fast for very large values:
this Calculator will show almost immediately that the number of digits in 10...0 with 40 zeroes
is itself a number with 42 digits(!)
Factorise factorial of
uses another very fast factorisation method. The complete prime factorisation of 1000000!
takes about a second.
Find the permutation with a given (range of) index number
Find the index number of a given permutation
The number of objects is the length of the permutation which must contain all the whole values between 1
and its length
Converting to and from the factorial base
When converting a factorial base representation to base 10, any whole (positive) values are allowed in any column;
when converting a base 10 value to factorial base, the legal form (no digit in column i is bigger than i) is used.
Factorial Base and Permutations C A L C U L A T O R
Which is the first factorial that is a multiple of
8 ?
17 ?
100 ?
8 = 23 and the three 2s as factors will come from 2 and two more from 4, so 4! is the first multiple of 8
17 is prime so if first appears in 17!
100 = 22 52 and these factors will come from 2, 4, 5 and 10,so 10! is the first factorial to end with 00.
2! is the first even factorial,
3! is the first factorial divisible by 3
4! is the first divisible by 4 and
5! the first that is a multiple of 5.
Which is the first divisible by 6?
And which factorials are the first divisible by 7, by 8, by 9 and by 10?
3! is the first multiple of 6
7 is a factor first in 7!
8 in 4!
9 in 6!
10 in 5!
The sequence of n where n! is the first divisible by 2,3,4,... is: 2,3,4,5,3,7,4,6,5, ... called the Kempner Numbers A002034
How many zeroes are at the end of:
10!
20!
100!
10! = 3628800 = 2×3×4×5×6×7×8×9×10
ends with 2 zeroes
20! = 2×...5×...10×...15×...20×
ends with 4 zeroes
100! has 5 as a prime factor from 5,10,15,20,...90,95,100 and more than enough even numbers to match these.
Each of these 20 numbers has one 5 as a factor except 25, 50, 75 and 100 which have 5×5 as a factor:
20 + 4 = 24 zeroes at the end
The Binomial Representation using Pascal's Triangle
Pascal's Triangle
Here is Pascal's Triangle but pushed over ("right justified") so that the 1s at the end of the rows are aligned in a column:
r
8
7
6
5
4
3
2
1
0
n
1
0
1
1
1
1
2
1
2
1
3
3
1
3
1
4
6
4
1
4
1
5
10
10
5
1
5
1
6
15
20
15
6
1
6
1
7
21
35
35
21
7
1
7
...
⋮
Notation:
(
n
)
= Binomial(n,r)
r
=
n!
(n-r)! r!
=
n(n−1)...(n−r+1)
r(r−1)...3×2×1
Here we will use Binomial(n,r) but other notations you will see in maths books are nCr, nCr or Cn,r
and it is pronounced "n choose r".
Each element in Pascal's Triangle above, which is right-justified here, is the sum of the element above
and the element to the right of that one where blank entries mean "0". The right-hand elements
in column 0 are always 1:
(
n
)
=
(
n − 1
)
+
(
n − 1
)
, n ≥ r > 0
r
r
r − 1
(
n
)
= 1;
(
n
)
= 0 otherwise
0
r
Pascal's Triangle has many interesting properties including coefficients of certain polynomials and
has many applications including probabilites.
The Binomial Representation
To use Pascal's triangle as an integer representation method,
you first decide on the number columns you want to use.
Then you choose one element from each column
and, to make the representation unique,
as we go to a smaller column number, we must choose an entry on a smaller row number too.
For instance, here is 6 represented using from 1 to 4 columns. Remember that we must choose a row for each of the N columns and as
N decreases so must the row numbers chosen. The Binomial representation is then just the list of row numbers in order of the column
numbers going down from N to 1.
All numbers in a Binomial base have their digits in decreasing order.
Notation
Once we have decided on the number of columns to use, it is the row number for each of the columns that forms the representation
as a list of the row numbers. To conform to the way other bases are shown, we list the row numbers from the largest down to 1.
Because the representation will change depending on how many columns we use,
the Base is shown as Binom.
The two examples above are therefore
Binomial(4,2) + Binomial(0,1) = 6 + 0 = 6 which is {4,0}
using 3 columns
Binomial(4,3) + Binomial(2,2) + Binomial(1,1)
= 4 + 1 + 1 = 6 which is {4,2,1}
using 4 columns
Binomial(5,4) + Binomial(3,3) + Binomial(1,2) + Binomial(0,1)
= 5 + 1 + 0 + 0 = 6 which is {5,3,1,0}
Note that all the column numbers are used in order and that the row numbers decrease as the column numbers decrease.
To convert from Binomial representation to its base 10 value:
Insert the column numbers after each 'digit', numbering the columns from 1 on the right going right to left
and then interpret these are arguments to the Binomial function: for example:
{5,3,1,0}Binom has its numbers paired with columns in order, ending with column 1:
row n
5
3
1
0
col r
4
3
2
1
(
n r
)
5
1
0
0
We then interpret this as Binomial(5,4) + Binomial(3,3) + Binomial(1,2) + Binomial(0,1)
which evaluates to 5 + 1 + 0 + 0 = 6 = {5,3,1,0}Binom
Using your answer to Question 1 what is {N+2, N+1, N-2, N-3, ... , 2, 1, 0}Binom
where the 'digits' from N-2 descend by 1 to end at 0?
{N+2, N+1, N-2, N-3, ... , 2, 1, 0} = 2 N − 1
Express 100=102 in base 9.
What is 103 in base 9?
How do your answers above relate to the Binomial Theorem?
Think about 10 as 9+1 and raise it to a power.
What is 103 in base 3 and how does it relate to its representation in base 9 above?
102 = (9 + 1)2 = 1×92 + 2×9 + 1 = 1219 = 81+18+1 = 100
103 = (9 + 1)3 = (9+1)3 = 13319
In general, the 'digits' of (β+1)n are the binomial coefficients of row n provided they are no bigger than the base.
Base β is related to base β2 by writing each base β2 'digit' as two base β digits:
1000 = 13319 = 01 10 10 01 3 because
39 = 103
References
Looking into Pascal's Triangle: Combinatorics, Arithmetic, and Geometry
P Hilton, J Pedersen Mathematics Magazine vol 60 (1987), pages 305-316
JSTOR
A nice article with lots of formulae that make great investigations for students to discover for themselves
Sums of Powers J Tanton Math Horizons vol 11 (2003), pages 15-20
JSTOR
Another excellent article for teachers and others
See Eric Weisstein's MathWorld (a Wolfram Web Resource) entry on
Binomial Coefficient
The Art of Computer Programming Vol 4a: Combinatorial Algorithms Part 1 D E Knuth. Page 360
refers to the Binomial representation system using t columns as the Combinatorial Number system of degree t and the following reference...
Ernesto Pascal, Giornale di Matematiche vol 25 (1887), pages 45-49 (in Italian).
Representation of Numbers by Cascades
C C Chen, D E Daykin, Proceedings of the American Mathematical Society (Vol 59, 1976), pages 394-398.
JSTOR
Number Bases and Binomial Coefficients J M Howell, R E Horton
Maths Mag 35 (1962) pages 177-179
The Fibonacci Bases
The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
where each is the sum of the previous two numbers.
It has many interesting mathematical properties.
As a number base system, we again label the columns in order increasing to the left: 8, 5, 3, 2, 1
with just a single column labelled 1 so we only use Fibonacci numbers with index 2 or more because Fib(2)=1, Fib(3)= 2, ... .
Every whole number is a sum of different Fibonacci Numbers
that is: no Fibonacci number is used more than once.
We can use F to signify a representation using the Fibonacci numbers as column headers.
3 = 100F = 2 + 1 = 11F
Since Fib(1) is 1, we can simply use n Fib(1)'s to sum to any given number n.
But there is always another way to do this too for numbers bigger than 1.
If we write the number of times we need Fib(i) is column i, we have a number representation whose 'digits' are
any whole number.
The minimal and maximal Fibonacci bases
However, if we restrict ourselves to using each Fibonacci number at most once
then it is again possible to find a collection which is a set of Fibonacci numbers whose sum is any given integer.
Two in particular are of interest: since Fib(n-1) + Fib(n-2) = Fib(n), then any two consecutive 1s in a
Fibonacci representation can be "carried" into the next column. It turns out it is always possible
to find a set of Fibonacci numbers with any given sum that
either never have two consecutive 1's - so we use the smallest set of Fibonacci numbers - the minimal
Fibonacci representation or Zeckendorf representation, which we write as Fmin
or never have two consecutive 0s - we use the largest set of Fibonacci numbers - the maximal Fibonacci
representation which we write as Fmax
Here are all the Fibonacci representation for numbers 1 to 9:
Columns in the Fibonacci base as ..., 8, 5, 3, 2, 1
Columns in the Fibonacci base are ...8 5 3 2 1
n
0
1
2
3
4
5
6
7
8
9
nF
0
1
10
100 11
101
1000 110
1001 111
1010
10000 1100 1011
10001 1101
To convert to and from Fibonacci bases
There are usually many Fibonacci representations of a number using only the 'digits' 0 and 1 in every column and with the column
headings (in reverse order): 1, 2, 3, 5, 8, 13, 21, ...
An easy method of converting a number to base F will give the Zeckendorf represenation which happens to have
the least number of 1s of all the Fibonacci representations for the number.
Write the Fibonacci column headings, in order from right to left, from 1,2,... until the column headings are
larger than the value to be converted
Start by writing the decimal number to be converted above the leftmost column header
If the column heading is larger than the number, put a 0 in that column and
keep the number to use on the next column on the right;
Otherwise if the column header is not larger than the number, Subtract the column header value from the number
and write a 1 in the column
repeat the step above on the same or, if you did the subtraction, the reduced decimal number
after the rightmost column you should have reached 0.
If not, you've made a mistake so check your previous steps!
Each column now has a 0 or 1 in it which is the Fibonacci (Zeckendorf) representation
For instance here we convert 52 to base Fibonacci:
A: number
52
18
18
5
5
0
0
0
B: Fib col heading
55
34
21
13
8
5
3
2
1
A-B or A
18
18
5
5
0
0
0
0
F digit
1
0
1
0
1
0
0
0
52 = 10101000F
To convert from base Fibonacci, write the column headings above the digits and add the column headings above each digit '1'.
We can also express every number positive and negative using only the negative indices in the Fibonacci series:
i
...
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
...
Fib(i)
...
-21
13
-8
5
-3
2
-1
1
0
1
1
2
3
5
8
13
21
...
The advantage is that now both positive and negative whole numbers can be represented without an initial sign.
We have to choose between using the negative indices to the right of a radix point (as in integer-valued bases)
but this has the disadvantage of having 0 digits at the front.
Since the values are not fractional, listing them with indices running from -1:...-4, -3, -2, -1 makes more sense.
For instance:
i
-5
-4
-3
-2
-1
F(i)
5
-3
2
-1
1
0
0
1
1
2
1
0
0
3
1
0
1
4
1
0
0
1
0
5
1
0
0
0
0
6
1
0
0
0
1
7
1
0
1
0
0
8
1
0
1
0
1
i
-6
-5
-4
-3
-2
-1
F(i)
-8
5
-3
2
-1
1
0
0
-1
1
0
-2
1
0
0
1
-3
1
0
0
0
-4
1
0
1
0
-5
1
0
0
1
0
1
-6
1
0
0
1
0
0
-7
1
0
0
0
0
1
-8
1
0
0
0
0
0
We add up the Fibonacci numbers for each column with 'digit' 1 in it to find the value represented.
Every integer value now has a representation using 0s and 1s only.
The above are minimal forms, using the least number of 1-digits. As for minimal Fibonacci representations (Zeckendorf representations)
there will never be two 1's next to each other.
Here we call this the Fibonacci Negative Index representation or
Fibnegi or just Fnegi.
How can we tell if a base Fibnegi value is negative?
The positive numbers start with an index of a positive Fibonacci number so are of even length.
The negative numbers start with an index of a negative Fibonacci number so are of odd length.
References
Zeckendorf Representations Using Negative Fibonacci Numbers M W Bunder
Fib Q vol 30, (1992) pages 111-115 PDF
Negative Bases
If we use base -10 (negadecimal) then the columns have the values
Column:
...
4
3
2
1
0
Meaning
...
(-10)4
(-10)3
(-10)2
(-10)1
(-10)0
Value
...
10000
–1000
100
–10
1
At first it may not be obvious that
Every whole number value, both positive and negative, has a unique representation
in base -10 (negadecimal) using just the digits 0 to 9 without needing a sign
For instance,
0 to 9 are as normal
10 = 100−90 = 190−10
11 to 19 are therefore
11=191−10,
12=192−10,
... ,
19=199−10
What are the first 5 column headers in base −2?
Make a table of numbers from −12 to 12
in base −2.
n10
-12
-11
-10
-9
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
n-2
110100
110101
1010
1011
1000
1001
1110
1111
1100
1101
10
11
0
1
110
111
100
101
11010
11011
11000
11001
11110
11111
11100
Using Negative Digits
Instead of using powers of a negative number base to represent negative values, we could use negative 'digits'.
This is not as peculiar as it might at first sound. For example if the time is 2:50 then we can say "10 to 3"
which is in effect using the hour 3 and the minutes -10.
We can also see times expressed with minutes from 0 to 59 (base 60) on timetables for example and, when saying the time
the minutes go from -29 to +30 as in "29 minutes to 3" up to "3:30".
So for base β instead of using 'digits' 0 to β−1
we could just as effectively use 'digits' −β/2 to
+β/2 if β is odd (rounding the halves).
To make sure representations are unique when β is even we can decide to
use either−β/2or elseβ/2 but not both 'digits'.
Using two symbols for negative digits is inconvenient (is 3−5 two 'digits' or a subtraction?)
so
to use one single 'digit' per column and we can show negative 'digits' with the
negative sign placed above the 'digit' so that −3 is written as 3.
Base −10 using the 10 'digits': 4, 3, 2, 1, 0, 1, 2, 3, 4, 5
0 .. 5:
0−10 .. 5−10
6 .. 15:
14−10 .. 15−10
16 .. 25:
24−20 .. 25−20
−4 .. −1:
4−10 .. 1−10
−16 .. −5:
24−10 .. 15−10
−26 .. −15:
34−10 .. 25−10
123 is 100 −20 −3 = 77
It is easy to see if a value represented using nega-digits is positive or negative.
Show how
If the leftmost 'digit' is positive, the value is positive;
if the leftmost 'digit' is negative, the value is negative
Also, it is easy to negate a value in this system.
Show how
Change each positive 'digit' into its negative form and vice-versa.
How are -9 to 9 represented in base 3 using the 'digits' 1, 0 and 1?
n
0
1
2
3
4
5
6
7
8
9
n3
0
1
11
10
11
111
110
111
101
100
m
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
m3
1
11
10
11
111
110
111
101
100
Rational Bases
Up to now we have only used whole numbers as our 'column headings' but always our 'digits' are whole numbers.
It is also possible to use column headings based on powers (a radix system) where the base is not a whole number but
a fraction (a rational) such as 3/2.
In base β, an integer,
when we add 1 to the units column and find a value equal to β, we take β away and add one (the carry) to the
next column to the left.
In a rational base, say 3/2, when we find 3 in any column we carry 2 to the column to the left. This applies
to any rational number β bigger than 1.
The 'digits' in rational base m/n are the digits of base m, namely 0
to m−1.
1 =
13/2
15/2
15/3
2 =
23/2
25/2
25/3
3 =
203/2
35/2
35/3
4 =
213/2
45/2
45/3
5 =
223/2
205/2
305/3
6 =
2103/2
215/2
315/3
7 =
2113/2
225/2
325/3
8 =
2123/2
235/2
335/3
9 =
21003/2
245/2
345/3
10 =
21013/2
405/2
3105/3
11 =
21023/2
415/2
3115/3
12 =
21203/2
425/2
3125/3
Here is how we convert 11 to base 3/2:
Divide 11 by 3 noting the remainder:
3 ) 11
3 rem =
2
Multiply the quotient 3 by 2
and divide it by 3
3 ) 6
2 rem=
0
Multiply the quotient 2 by 2
and divide it by 3
3 ) 4
1 rem=
1
Multiply the quotient 1 by 2
and divide it by 3
3 ) 2
0 rem=
2
STOP because
The number is now 0 and
all future 'digits' will be 0.
Read the remainders from bottom to top
21023/2
Rational bases less than 1
For rational base β less than 1 (but bigger than 0), reverse the digits of the representation
in base β remembering to include the radix point. This is because (β)n is (1/β)−n.
For example:
12 = 3125/3 = 2.133/5
Use the Base Converter below to convert to and from rational bases.
Rational base 2 is not the same as base 4/2
Since our algorithm to convert a number to a rational base produces 'digits' of the numerator as a base, then
base 4/2 produces a number using 'digits from the list 0,1,2,3
whereas base 2/1 produces 'digits' from 0,1!
For example 23 in base 2 is 101112.
All conversions to base 2 are the same as to base 2/1.
But in base 4/2 we have 20234/2 = 2310.
In base p/q where p/q is in its lowest terms every number has a unique representation.
But in a non-simple rational base p/q = b (a base that is a fraction p/q but
p is a multiple of q and so the base simplifies to the number b)
every number from b upwards has more than one representation
In base 4/2, the column's values are 8=(4/2)3, 4=(4/2)2, 2=4/2 and 1
and the digits we can use are 0, 1, 2, 3. So 8 has 5 representations:
8 = 3×2 + 2×1 = 324/2
8 = 1×4 + 1×2 + 2×1 = 1124/2
8 = 1×4 + 2×2 = 1204/2
8 = 2×4 = 2004/2
8 = 1×8 = 10004/2
What we have found are the 5 partitions of 8 into bags (or multisets which are
sets but with repetition allowed) using the
parts 1,2,4 and 8 (columns of base 2, the base in simplest terms) up to a maximum of 3 times each (the remainders mod 4, the base numerator).
Some Combinatorics Of Rational Base Representations
T Edgar, H Olafson, J Van Alstine, preprint (2017)
pdf
Proof that if p and q have no common factor then every number has a unique representation in base p/q.
Negative Rational Bases
We ensure that all remainders are non-negative when dividing a number by the numerator.
The denominator of the base is always a positive number.
For example, 5 ÷ −4 is −1 with remainder 1
because 5 = −1×−4 + 1.
RULE: For all b>0 : a ÷ b = q remainder r
if and only if
a = b×q + r and 0≤r<b
Here is how we convert 5 to base −4/3 by repeatedly dividing by −4 (the numerator),
noting the reminder, then multiplying the quotient by 3 (the denominator):
Divide 5 by −4 noting the remainder:
−4 ) 5 −1 rem =
1
Multiply the quotient −1 by 3
and divide it by −4
−4 ) −3 1 rem =
1
Multiply the quotient 1 by 3
and divide it by −4
−4 ) 3 0 rem =
3
STOP because
The number is now 0 and
all future remainders will be 0.
Read the remainders from bottom to top
Convert 23 to bases 6/3 and 8/4.
Can you find a method of converting easily from one fractional base to
another whose fraction simplifies to the same number?
Make a table of the number of base 3/2 digits in numbers 0 to 30.
Find a recursive formula for the digit count.
Length is 1 for numbers 0,1,2,3
Length is 2 = length(23/2)+1 for 3,4,5
Length is 3 = length(43/2)+1 for 6,7,8
Length of n is length(2 Floor(n/3))+1 in general.
See A246435
The number of digits in number n is one more than the number in 2 Floor(n/3) where
for positive n, the Floor(n) is n if n is an integer otherwise it is the nearest integer below n.
For positive n, the floor of n is just n without any digits after its decimal point.
How many numbers have 1 digit in base 3/2? How many have exactly 2 digits? and length 3?
3 have 1 digit, 3 have 2, 3 have 3 ....
The list of the counts is
3, 3, 3, 6, 9, 12, 18, 27, 42, ... A081848
Which is the smallest number to have exactly n base 3/2 digits?
The smallest with 1 digit is 1 (or 0), with 2 digits is 3, with 3 digits in 6:
1, 3, 6, 9, 15, 24, 36, ... A070885
Which is the smallest even number to have n digits in base 3/2?
List them with their base 3/2 representations.
What simple pattern connects the representations?
The base 3/2 reps are
n3/2
n
2
2
21
4
210
6
2101
10
21011
16
210110
24
2101100
36
21011000
54
They all are extensions of the previous one, adding one new digit on the right
A303500.
The infinite sequence of which each representation is an initial part is A304273
and the numbers themselves are in A305498
What is the largest even number that can be written with n base 3/2 digits?
What are their base 3/2 representations?
n
n3/2
2
2
4
21
8
212
14
2122
22
21221
34
212211
52
2122111
80
21221112
The numbers are A305497 their representations are A304272
Each is a single digit extension of the previous one so that their representations
are the initial part of the infinite sequence
21221112212112212121.... A304274
Irrational Bases
But what if our column headings were powers not of a whole number nor even a rational number but
of an irrational number, such as Phi, the golden section number or √2? This also works
with some conditions on the base and the 'digits'.
Let's look at an example: base Phi.
Base Phi (Φ)
Phi is 1.6180339... = (√5 + 1)/2, one of the golden section numbers (or golden mean or golden ratio).
Because Phi2 = Phi + 1 is a definition of the positive number Phi, we only need "digits"
0 and 1, called "phigits"!
The basic Phi rule is Phin+2 = Phin+1 + Phin
All natural numbers are representable in Base Phi using phigits 0 and 1 but we will need negative powers
and so we need a "base point" to act like the decimal point in base 10.
Just as for Fibonacci base numbers above, we need never have two 1's next to each other since they combine to give a 1
in the next column to the left using the basic Phi rule.
Here Phi = 1·6180339... = phi–1
and its reciprocal (1/Phi) is also the same as Phi−1 which onthese pages is denotes
by the lower case Phi: phi = 0·6180339... = Phi – 1 = 1/Phi = Phi–1
Column
Phi power
phi power
A + B Phi
C + D phi
real value
5
Phi5
phi-5
3 + 5 Phi
8 + 5 phi
11·0901699..
4
Phi4
phi-4
2 + 3 Phi
5 + 3 phi
6·8541019..
5
Phi3
phi-3
1 + 2 Phi
3 + 2 phi
4·2360679..
2
Phi2
phi-2
1 + 1 Phi
2 + 1 phi
2·6180339..
1
Phi1
phi-1
0 + 1 Phi
1 + 1 phi
1·6180339..
0
Phi0
phi0
1 + 0 Phi
1 + 0 phi
1·0000000..
-1
Phi-1
phi1
-1 + 1 Phi
0 + 1 phi
0·6180339..
-2
Phi-2
phi2
2 - 1 Phi
1 - 1 phi
0·3819660..
-3
Phi-3
phi3
-3 + 2 Phi
-1 + 2 phi
0·2360679..
-4
Phi-4
phi4
5 - 3 Phi
2 - 3 phi
0·1458980..
-5
Phi-5
phi5
-8 + 5 Phi
-3 + 5 phi
0·0901699..
For instance 2 is 10.01Phi = Phi + Phi−2.
1..13 in base Phi
1
1
.
Phi
2
10
.
01Phi
3
100
.
01Phi
4
101
.
01Phi
5
1000
.
1001Phi
6
1010
.
0001Phi
7
10000
.
0001Phi
8
10001
.
0001Phi
9
10010
.
0101Phi
10
10100
.
0101Phi
11
10101
.
0101Phi
12
100000
.
101001Phi
13
100010
.
001001Phi
phi = 1/Phi = Phi-1 = 0.6180339... = (√5-1)/2 and the basic phi rule
is phin = phin+1 + phin+2.
Because Phi−n = phin
it is easy to see that to get a base phi representation from a base Phi representation
we merely reverse the order of the phigits
including the base point:
A Number System with Irrational Base, George
Bergman, Mathematics Magazine 1957, Vol 31, pages 98-110, where he
also gives pencil-and-paper
methods of doing arithmetic in Base Phi.
C. Rousseau The Phi Number System Revisited
in Mathematics Magazine 1995, Vol 68, pages 283-284.
Other irrational bases: √n
If n is not a square number then
the even powers of √n are just the powers of n so base √n includes all the representations
of integers in base n.
Columns for base β=√n
...
β6
β5
β4
β3
β2
β1
β0
...
n3
n5/2
n2
n3/2
n
n1/2
1
...
n3
n2√n
n2
n√n
n
√n
1
The table shows that
the √n values are in the odd-power places
the purely integer values are in the even-power places
Because √n is itself not rational, the only values we can represent in base √n
are A + B√n for whole numbers A and B.
If we represent A in base n then shifting all its digits one place left will effectively multiply the value by the base, √n.
So any value A √n will only have non-zero digits in the even-power places and always 0s in the odd-power places.
We can then 'add' in the digits of B in base √n which similarly will have only
0s in the odd-power places and any non-zero digits will be in even-powered places.
5 = 1012
which in base √2 becomes 5 = 10001√2 = 10001√2
Similarly 7 = 1112
which in base √2 becomes 7 = 10101√2 = 10101√2
Shifting the digits of 7's representation one place to the left multiplies the value by √2: 7√2 = 10101 0√2
Adding the representations of 5 and 7√2 is easy because there are never any 'carries':
Columns
4√2
22
2√2
2
√2
1
5
=
1
0
0
0
1
7 √2
=
1
0
1
0
1
0
5 + 7√2
=
1
1
1
0
1
1
5 + 7√2 = 111011√2
Base Converter
About the Base Converter Calculator:
Numeric bases
Bases can be any integer, positive or negative except -1, 0 and 1
fractional bases are input as N/M with the "/" symbol separating the two whole numbers N and M.
Other bases
F which is the same as Fmin: the Fibonacci base with the minimum number of 1s known as the
Zeckendorf representation
Fmax: Fibonacci base but using the maximum number of 1s
Fnegi: Fibonacci Negative Index with the indices increasing to the right.
Phi Phi=1.618...=(√5+1)/2. The same as Phimin: base Phi with the minimum number of 1s (...11... never occurs)
Phimax base Phi but using the maximum number of 1s (...00... never occurs)
phi phi=0.618...=(√5−1)/2. The same as phimin: base phi with the minimum number of 1s (...11... never occurs)
phimax base phi but using the maximum number of 1s (...00... never occurs)
!: Factorial base
BinomN where N is a whole number. The N can be left out if converting
from a Binomial representation (as it is the length of the list of 'digits')
but is needed if converting to a Binomial base.
'Digits':
'Digits' in between { and } brackets can be any integers, including negative values
for example {12,-3,0} . The { } may not be omitted.
A negative number in a positive base is written with negative digits.
5 in binary is 101. -5 in binary is -101 which is written in the Calculator as {-1,0,-1}
An integer base can have balanced digits so that has 'half' its digits negative and 'half' positive
Radix point:
A 'decimal point', called a radix point in bases other than 10,
if using { } notation is inserted just as it is, for example {1,2,.,3,4}
in Fibonacci bases, we use only the columns indexed from 2 upwards corresponding to Fibonacci numbers ..8,5,3,2,1.
If a radix point is used, 'digits' after the radix point refer to Fibonacci numbers with indices -2,-3,-4,...
and the radix point separates the positive indexed digits from the negative:
i
5
4
3
2
1
0
-1
-2
-3
-4
-5
●
Fib(i)
5
3
2
1
1
0
1
-1
2
-3
5
Different answers?
There is no check on the validity of 'digits' when converting to base 10:
3212 means 3×22 + 2×21 + 1 = 17
and similarly for the other bases.'Digits' can be negative or any whole number.
However on converting from base 10 to another base, the 'digits' will be valid for that base.
Converting 17 to base 2 will give 100012
and similarly for the other bases
Make a table
To make a table of conversions of a number to a range of bases, put the number in the from box
and list the bases separated by a comma.
Click on
to make a table of a numbers converted to one base, fill in the from and to input boxes and
put the base in the converted to these bases box.
Click on
You can also specify a range of numbers and a list of bases to convert them all to.
Need more space for numbers?
Resize the Result box and the input boxes for conversion to and from base 10
by grabbing a corner with the mouse.
On devices without this facility:
Use the
and
buttons to
expand or decrease the input box height
We can solve many problems on integers by looking at their remainders when divided by a divisor. So the list of numbers having a remainder of 2 when divided by 5 is
2, 7, 12, 17, 22, .... We write this as x ≡ 2 (mod 5) read as "x is equivalent to 2 mod 5" and meaning
x has a remainder of 2 when divided by 5 We do not use the equal symbol since there are many answers for x but use
the equivalent symbol ≡ with three lines.
An old problem
Suppose we are observing a company of soldiers on the march.
They move quickly and we only have time to note that when marching down the road
in rows of 15 there were 8 men left over at the back.
When they came to a narrow bridge, they re-formed into rows of 8 and 2 men were left
at the back.
Can you work out the probable number from these two facts?
This is an example of an ancient puzzle to find a number when we are told its remainders
when divided into several different sizes.
In this section we see how we can use this as a system of counting or representing numbers and, given such a list of remainders
and the divisors, how can we find an number that fits.
Using remainders to count
This is a system which has many computational advantages, particularly for computers that can run several
computations in parallel
since each 'digit' is independent of the others.
If we have the remainders of a number when dividing it by a series of
divisors (each is called a modulus with plural modulii and usually written mod for short),
all of which are numbers bigger than 1, we
can then reconstruct the original number.The simplest case is when no two divisors have a factor in common but it can be solved, sometimes
if there are divisors with factors in common.
For example 13 has a remainder of 1 when divided by 3, but so do 4, 7, 10, 13, 16, 19, 22, 25, 28... .
Of these, 13 is the first with a remainder of 3 when divided by 5.
The next number with these two remainders (1 and 3) mod 3 and 5 is 28.
All of them are multiples of 15 plus 13 but
13 is unique up to 3×5 = 15.
We write this as 13 ≡ 1 (mod 3); 13 ≡ 3 (mod 5) and the solution is given by the single congruence: x ≡ 13 (mod 15).
By working with pairs of congruences we can reduce each pair to a single congruence and hence
we can also extend this method to any number of divisors.
This will mean we can easily recover the original number from the list of remainders and modulii
and it will be unique up to the product of all modulii if no two divisors have a factor in common.
If we use small divisors such as only primes divisors (then clearly no two have a factor in common)
we can uniquely represent each integer by its list of remainders, up to the limit which is the product of all the divisors.
The more divisors we use, the larger the range of unique remainders will be.
To extend the range in our example up to 100, then we can use modulus 7 as well (so that the product
3×5×7 = 105>100)
or perhaps use the prime 2 also:
Solve the problem given at the start of this section. The small army had N personnel where
N = 8 (mod 15) and N= 2 (mod 8).
Find the smallest solution. Can we determine the exact size if it was less than 200?
38 is the smallest number, 38=8+2*15 = 2+9*4.
The pair of remainders (8 and 2) will the same for any multiple of 15×4=60 beyond this:
38, 98, 158, 218, ...
Since the army was under 200 strong, then two answers are possible: 98 and 158.
Sun-Tsu lived in China around 100 AD and wrote books about warfare. He posed the following problem and showed a method of finding the
answer:
A number of objects when counted in threes leaves 2 left over.
When counted in fives, there are 3 left over.
If arranged in groups of 7 there are again 2 left over.
How many objects were there?
x = 2(mod 3), x=3 (mod 5), x=2 (mod 7). 3,5,7 are co-prime.
The smallest answer is 23 but these remainders repeat in gaps of 105.
Another ancient problem:
A woman has a basket of eggs to take to the market. If taken out in twos, there was 1 left over.
If she took them out three at a time there was also one left over, and also if she took them out in fours, fives and sixes.
If she had more than one egg, how many were in her basket?
Fibonacci extended this problem in his Liber Abaci of 1202.
When she took out the eggs in sevens, none were left in the basket. How many eggs did she have?
Using 5 of the modulii, 2, 3, 4, 5 and 6, whose lcm is 60, then 61 is the likely solution.
Solving x≡1(mod 60) and x≡1( mod 7) gives 301 (mod 420)
How to find the base 10 value of a Remainders Number
The conversion relies on an ancient algorithm devised by Euclid to find the greatest common divisor of two numbers. We then use this to
solve two simultaneous congruences.
Euclid's Algorithm
Euclid's Algorithm is a method of finding the greatest common divisor (gcd) of two numbers. It also has the
function of finding two numbers A and B so that when we know g=gcd(M,N) then it also produces an A and a B such that
A×M + B×N = g.
For example:
Find the gcd of N=25 and M=35:
Starting from M/N putting the larger M on top and keep finding the smallest remainders dividing first by N for first remainder then of the lastest two remainders
until we find a remainder of 0:
35 = 1×25 + 10 25 = 2×10 + 5 10 = 2×5 + 0
The last non-zero remainder was 5 and this is the gcd of 35 and 25.
We can find the A and B to make A M + B N = 5 by including two extra columns to
update the A and the B values for each quotient we find as shown here for gcd(235, 50):
Find gcd(235, 50)
i
quotients
& remainders
Ai
Bi
i
Find qi
Ai = Ai-2- qiAi-1
Bi = Bi-2- qiBi-1
1
start
A1 = 1
B1 = 0
2
start
A2 = 0
B2 = 1
3
235 = 4×50+ 35
A3 = 1 - 4× 0 = 1
B3 = 0 - 4× 1 = -4
4
50 = 1×35 + 15
A4 = 0 - 1×1=-1
B4 = 1 - 1×(-4) = 5
5
35 = 2×15 + 5
A5 = 1 - 2×(-1) = 3
B5 = -4 - 2×5 = -14
15 = 3×5 + 0
A5×235 + B5×50 = 5 3×235 + (-14)×50 = 5
If we find the gcd of two relatively prime numbers (whose gcd is 1) then we can alsop solve the division problem that we saw in the Arithmetic section above.
Since gcd(7,5) = 1 and also Euclid's Algorithm tells us that -2×7 + 3×5 = 1 then we can take this whole equation modulo 7 and modulo 5:
-2×7 + 3×5 ≡ 1 (mod 7)
3×5 ≡ 1 (mod 7)
So to divide by 5 (mod 7) as the opposite of multiply by 5 (mod 7)
we need only multiply by 3 (mod 7). Apart from 0 every number 1 to 6 has an inverse denoted by n-1:
n
0
1
2
3
4
5
6
n-1
-
1
4
5
2
3
6
n×n-1
-
1
1
1
1
1
1
To find the multiplicative inverse of m (mod n) then if gcd(m,n)=1 we can use Euclid's Algorithm to
find A×m + B×n = 1 and so, mod n, we have A×m ≡ 1 (mod n). A will always exist if gcd(m,n)=1
and only in that case.
We will solve the general case for two modulii m and n when gcd(m,n)=g need not be 1.
We find the general solution for x when
x ≡ a (mod m) and x ≡ b (mod n)
Alongside we will illustrate with the example
x ≡ 14 (mod 30) and x ≡ 34 (mod 50).
General case
Example
x ≡ a (mod m) and x ≡ b (mod n)
x ≡ 14 (mod 30) and x ≡ 34 (mod 50)
These two equivalences give us two simultaneous equations:
x = a + K×m and x = b + L×n for some integers K and L
x = 14 + K×30 and x = 34 + L×50
Subtracting the two equations :
K×m - L×n = b - a (*)
K×30 - L×50 = 34-14 = 20 (*)
Therefore if the gcd of m and n is g then by Euclid's Algorithm
we can find A and B where
A×m + B×n = g (**)
2×30 + (-1)×50 = 10 = g (**)
Suppose then that b-a is a multiple of g
let (b-a) = q×g
(b-a)=34-14=20=2×10=2×g q=2
Multiply (**) through by q :
q×A×m + q×B×n = q×g = b - a
2×30×2 + (-1)×50×2 = 10×2 = 20
so we have found two values for K and L in (*):
K=q×A and L=q×B.
K=2×2=4, L=2×1 = 2
Substituting back into our original two equations for x:
x = a + K×m = b + L×n
x = 14 + 4*30 = 34 + 2×50 = 134
which is the value of x in base 10, modulo (m×n/g)
x = 34 (mod 150) because 150 = 50×30/10
We have thus reduced two simultaneous congruences to one.
If there are more congruences then we choose one more to pair with the new one and solve that by the
same process. We can do this until we find one single congruence for x. It will gives us
one value for x and a modulus (the lowest common multiple of all the modulii) to find the larger
solutions.
Sun-Tsu, a chinese military tactian and writer, solved the problem given in the Things To Do
section around 100 AD though without proof and without giving details of how to solve it.
A theorem, proved much later and extended, states when a set of simultaneous (linear)
congruences can be solved is names in his honour
The Chinese Remainder Theorem.
if all the modulii are co-prime in pairs (no two share a factor in common)
then there is always a solution which repeats with a gap
equal to the product of the modulii.
The Extended Chinese Remainder Theorem extends this to all moduli:
The Extended Chinese Remainder Theorem
if for all pairs of the equivalences we have
x≡a(mod n) and x≡b (mod n) if and only if
a≡b (mod lcm(m,n))
then there is a solution for x modulo the lcm of the modulii.
If the condition is not met for one pair of modulii then there is no solution.
Arithmetic in the Remainders System
There are some advantages to using this system to represent numbers:
The remainders used are small
Including more small modulii will extend the range
Arithmetic (+, − ×) is fast as all remainders can be computed separately, in parallel
The disadvantages are that it is more difficult to convert back to a decimal number and that division takes longer.
There is also the problem of catching 'overflow' when a number becomes too large to represent. However, this can be solved by
including more relatively-prime modulii until the lcm of the moduli exceeds any size of value likely to be encountered.
a+b (mod m) = a(mod m) + b(mod m)
a−b (mod m) = a(mod m) − b(mod m)
a×b (mod m) = a(mod m) × b(mod m)
so we can operate on each 'digit' (remainder) in a pair of representations to compute their sum, difference and product without
having to convert back to base 10:
Using modulii 2, 3, 5 and 7:
2
3
5
7
103 =
1
1
3
5
17 =
1
2
2
3
103+17 =
1+1
1+2
3+2
5+3
0
0
0
1
=120
103−17=
1-1
1-2
3-2
5-3
0
2
1
2
= 86
103×17
1×1
1×2
3×2
5×3
1
2
1
1
= 71
Note that the product exceeds the range of unique representations (from 0 to 209) so it is
the product but reduced mod (210).
Although we can easily test for equality,
it is not easy to compare two numbers in this system.
Why not division too?
There are several problems with division.
8 = 18 (mod 5). If we divide by 6, while 18/3=6 (=1 (mod 5) in the right hand side, on the left-hand side
we have 8/3 which is a fraction
10 = 2 (mod 8) but we cannot cancel (divide by 2) because 5=1 (mod 8) is wrong/li>
Instead, we could think of division as the opposite of multiplication, multiplying by the inverse of 4.
In ordinary arithmetic, this means dividing by 4 is the same as multiplying by 1/4 since 1/4×4 = 1.
In terms of our modular arithmetic, the inverse of 4 is a number that when multiplied by 4 (mod m) gives 1 (mod m), if such a number exists.
This exists if m is 5, say since the inverse of 1 is 1, the inverse of 2 is 3, the inverse of 3 is 2 and the inverse of 4 is 4.
As in ordinary arithmetic we cannot divide by 0 since there is no number which when multiplied by 0 gives 1 for any modulus.
In base 6, the inverse of 1 is 1 (as it is in all basees) but there is no number which is the inverse of 2 in base 6,
or in other words there is no number that when multiplied by 2 gives 1 (mod 6).
Fill in this table with entries 2M-1(mod 2N-1) for M and N from 1 to 6:
2M-1(mod 2N-1)
N
1
2
3
4
5
6
7
8
2N-1
1
3
7
M
2M-1
1
1
2
3
3
7
4
5
6
7
8
2M-1(mod 2N-1)
N
1
2
3
4
5
6
7
8
2N-1
1
3
7
15
31
63
127
255
M
2M-1
1
1
0
1
1
1
1
1
1
1
2
3
0
0
3
3
3
3
3
3
3
7
0
1
0
7
7
7
7
7
4
15
0
0
1
0
15
15
15
15
5
31
0
1
3
1
0
31
31
31
6
63
0
0
0
3
1
0
63
63
7
127
0
1
1
7
3
1
0
127
8
255
0
0
3
15
7
3
1
0
Form a conjecture about the entries if the table was extended indefinitely.
All the entries are of the form 2K−1
Fill in the table again but this time use the power K for each entry 2K-1.
Form a conjecture as to the relationship betwen M, N and these new entries.
N
1
2
3
4
5
6
7
8
2N-1
1
3
7
15
31
63
127
255
M
2M-1
1
1
0
1
1
1
1
1
1
1
2
3
0
0
2
2
2
2
2
2
3
7
0
1
0
3
3
3
3
3
4
15
0
0
1
0
4
4
4
4
5
31
0
1
2
1
0
5
5
5
6
63
0
0
0
2
1
0
6
6
7
127
0
1
1
3
2
1
0
7
8
255
0
0
2
4
3
2
1
0
Conjecture: The entries are M (mod N)
Show that 2M − 1 (mod 2N − 1) = 2M(mod N) − 1
Show that gcd(2M − 1, 2N − 1) = 2gcd(M,N) − 1
Show that the two neighbouring Fibonacci numbers Fib(n) and Fib(n+1) are always relatively prime.
Comment: No two smaller numbers will have more steps in Euclid's algorithm than two neighbouring Fibonacci numbers.
(Proved by Lamé in 1845 (see D Knuth Vol 2, section 4.5.3)
The maximum integer (MAXINT) that JavaScript can represent exactly is 253−1.
Therefore the maximum two integers it can multiply exactly (call it MAXMULT) are less than √(253−1).
What are the the largest 4 primes less than MAXMULT?
Using Remainders representations with these 4 primes as modulii, what is the maximum number we can
now represent exactly?
MAXINT = 253−1 = 9007199254740991
so all integers of up to approximately 16 digits
can represented exactly in JavaScript.
MAXMULT = √9007199254740991 = 94906265.62
so any two integers up to 94906265 (8 digits) will have exact (integer) products.
The 4 primes just less than 94906265 are 94906171, 94906213, 94906219 and 94906247.
The LCM of these 4 primes is 81129456763880539807161366209339 which has 32 digits
One less than this is 81129456763880539807161366209338 and is
the largest number we can represent exactly using these 4 modulii.
so with Remainders modulo these 4 primes, using remainders of up to 8 digits,
we can add, subtract and multiply exactly to get integer results of up to 32 digits.
An Application
When counting electronically, if we use the binary system with, say, 16 bits, then by adding one we sometimes find several carries
are needed. This was used in a radar system on the UK ships in the Falklands conflict of 1982. The French missiles, used by Argentina
sent out rapid pulses to home in on a target. The UK system counted the number of pulses to work out which kind of missile
was heading towards them. But the binary systems could not cope and one ship was sunk.
The answer lay in representing the numbers using several different modulii. Then each pulse added one to all the remainders
in parallel and the remainders were small.
References
The Thirteen Books of Euclid's Elements, Books 3 to 9 version by T L Heath (Dover paperback, 2nd edition, 2000)
Book 7 of The Elements starts with two propositions that are equivalent to
the algorithm for finding the greatest common divisor (gcd), also called the highest
common factor (hcf) of two numbers. The Elements date back to about 300 BC but was probably much older.
The Art of Computer Programming,
Vol 2: Seminumerical Algorithms D E Knuth
(first edition 1981, third edition 1997) especially section 4.5.2 and section 4.3.2 on Modular Representations, his name for
our Remainders Representations. He has an interesting section on how to make a practical computer system based on
this number system if separate moduli are implemented in binary circuitry and a fast way of converting
back to base 10 for fixed moduli.
Monotonic numbers
For a given base, Monotonic numbers are those that have all their base digits already in order, from least to most, left to right,
repetitions allowed. This is sometimes called non-decreasing order since any digit
must be less than or equal to the digit in the next
column to its right. In this section we investigate the monotonic numbers in base 10:
13 and 112 are monotonic but 103 and 192 are not monotonic.
You Do The Maths...
How many monotonic numbers are there between 1 and 10?
How many monotonic numbers are there between 10 and 100?
How many monotonic numbers are there between 100 and 1000?
1 to 9: all are monotonic: 9 numbers
10 to 100:
11 to 19, 22 to 29, ... 88-89, 99: 9+8+7+6+5+4+3+2+1 = 45 numbers
13 and 112 are monotonic numbers. 13×112= 1456 is also monotonic
33366667 and 333667 are monotonic and their product is 33366667×333667 = 11122255677889, also monotonic.
Here is a method to find pairs of monotonic numbers whose product is also monotonic:
Take two numbers each of which is either composed solely of 3s or has only 6s as its digits or with some 3s first followed by some 6s.
Add 1 to both numbers
Their product is monotonic
For example: (33+1)×(366+1) = 34×367 = 12478 a monotonic number.
Can you find any other examples that are not formed by the above method?
All are of the form above: see the Blecksmith and Nicol Reference below
5, 35 and 335 are monotonic.
Their squares are also monotonic: 52 = 25, 352 = 1225 and 3352 = 112225.
What is the pattern here?
5, 35, 335, 3335, 33335, ... any number of 3s followed by 5
have a monotonic square.
See the Blecksmith and Nicol Reference below
There is another similar pattern starting with 17. What is it?
17, 167, 1667, 16667, ... begin with 1, then any number of 6s and a final 7
all have monotonic squares.
This series and the one above are the only numbers with monotonic squares.
See the Blecksmith and Nicol Reference below
References
Monotonic numbers R Blecksmith, C Nicol,
Maths Mag vol 66 (1993) pages 257-262
Complex Number Bases
We can again extend our possible bases in a radix system to complex numbers and find a unique way to
represent integers and other values.
...... more coming soon .....
Links and References
An Introduction to Computational Combinatorics
E S Page, L B Wilson (1979 Cambridge)
see chapter 5 on several ways of ordering permutations as well as the factorial representation method of
generating them in lexicographic order.
Some theorems on Completeness V E Hoggatt, B Chow Fib Quarterly, vol 10 (1972)
pages 551-554,
560.
How can we decide if a given sequence of numbers could be used as the column headings of a base to
represent every whole number? This paper gives two theorems.
Systems of Enumeration A Fraenkel, Amer. Math. Monthly vol 92 (1985), pages 105-114
JSTOR
A proof of the existence and uniqueness of representations of positive integers in any system of "column headers"
described by a recurrence relation. This includes base β (powers of β) and mixed radix, factorial base, our Pascal's
triangle combinatorial system above as well as various systems based on the Fibonacci numbers.
Powers of rationals modulo 1 and rational base number systems
S Akiyama, C Frougny, J Sakarovitch
Israel J Math vol 168 (2008), pages 53-91
pdf
Some Combinatorics of Factorial Base Representations
T Ball, P Dalenberg, J Beckford, T Edgar, T Rajabi
Journal of Integer Sequences Vol. 23 (2020), Article 20.3.3
pdf
icon means there is a
You Do the Maths... section of questions to start your own investigations.
The 
calculator icon
indicates that there is a live interactive calculator in that section.
© from 2017 Dr Ron Knott
Dr Knott's Maths Fibonacci and HOME page